import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstPaths {
	private static final int INFINITY = Integer.MAX_VALUE;
	private boolean[] marked;  // marked[v] = is there an s-v path
	private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path
	private int[] distTo;      // distTo[v] = number of edges shortest s-v path

	/**
	 * Computes the shortest path between the source vertex <tt>s</tt>
	 * and every other vertex in the graph <tt>G</tt>.
	 * @param G the graph
	 * @param s the source vertex
	 */
	public BreadthFirstPaths(Graph G, int s) {
		marked = new boolean[G.numberVertices];
		distTo = new int[G.numberVertices];
		edgeTo = new int[G.numberVertices];
		bfs(G, s);
	}

	// breadth-first search from a single source
	private void bfs(Graph G, int s) {
		Queue<Integer> q = new LinkedList<Integer>();
		for (int v = 0; v < G.numberVertices; v++) 
			distTo[v] = INFINITY;
		distTo[s] = 0;
		marked[s] = true;
		q.offer(s);

		while (!q.isEmpty()) {
			int v = q.poll();
			// for (int w : G.adj(v)) {
				//    if (!marked[w]) {
			//        edgeTo[w] = v;
			//         distTo[w] = distTo[v] + 1;
			//        marked[w] = true;
			//        q.offer(w);
			//    }
		}
	}


	/**
	 * Is there a path between the source vertex <tt>s</tt> (or sources) and vertex <tt>v</tt>?
	 * @param v the vertex
	 * @return <tt>true</tt> if there is a path, and <tt>false</tt> otherwise
	 */
	public boolean hasPathTo(int v) {
		return marked[v];
	}

	/**
	 * Returns the number of edges in a shortest path between the source vertex <tt>s</tt>
	 * (or sources) and vertex <tt>v</tt>?
	 * @param v the vertex
	 * @return the number of edges in a shortest path
	 */
	public int distTo(int v) {
		return distTo[v];
	}


}